NOIP2020 总结 & 题解
写在 NOIP2020 之后
T3 构造我直接傻眼，搞了俩小时一分没得（这构造本质是模拟）。最近大赛考非正常题越来越多了，对码力的要求也逐步上升，这俩我都不擅长。对而且我还不擅长思维题。我擅长啥呢？套路题（有手就行的 sb 题）。
想要多写 LOJ 的神题、套路题、非正常题，想学生成函数。在役的时间，有一天便看一天的风景，dp 套 dp、生成函数这些人类智慧不看会后悔的吧 qvq？ 向前跋涉吧！“永远不要用行为上的努力来掩盖思维上的懒惰。”
成绩出了
丧气话删了。“世上一切不幸都是由于当事者能力不足”
题解
T1
先 乘 后 除 /吐血 痛失 30 分，痛失高一赛季！
正解就维护指数
T2
好吧。。这题就是复杂度优化题。后面东西用树状数组我做到了，前面那个用倍增我真想不到啊。。
肯定要枚举 AB，然后发现确定了 AB 的长度，C 的奇数个数只有 2 种值，就很简单了。
T3
据说我写的是 $70$ 分，就每次挑两个柱子，当前柱有 $x$ 个黑，$y$ 个白（显然颜色不重要，我们就看作黑白），然后把两个柱子准备一下，即一个留 $x$ 个空位，一个留 $y$ 个空位，但我调了很久，还写挂了，痛失 $70$ 分。赛后看题解知道自己只想到了几个关键细节中的一个。
我们钦定总有一个柱子是空的，即每次操作完，有 $n$ 个柱子都是满的，这样可以简化很多。（第二个细节）
先看 $n = 2$ 的情况。发现可以在不改变其他柱子状态的情况下整理一个柱子，即白的在下，黑的在上。（第三个细节）
然后可以将柱子整理成同色的，具体就是，通过空柱子，我们可以 $reverse$ 一个柱子；两个柱子选一种颜色的球，需要保证两个柱子上此颜色的球数之和 $\leq m$，给丢到空柱子上，用一个柱子上的球填满另一个柱子再将塞到空柱子上的球拿回放在这个柱子上。（第四个细节）
$n > 2$ 的情况分治就好了，复杂度 $O(5nmlogn)$，极限数据只跑了 $500000$。
需要注意的是，可能存在一个柱子颜色全是黑或全是白，merge 的时候可能会 $> m$，需要特判。
T4
暴 力 写 挂 我是屑
又是构造又是多项式的，爽啦。
对于暴力和正解都很重要的一个思想：每维是独立的。
如果模拟两轮没走完，发现每轮合法位置的变化量是线性的，即对于第 $i$ 维，第一轮走了 $a_i$，第二轮走了 $b_i$，那么再走 $x$ 轮减少的就是 $b_i - (a_i - b_i) * x$
枚举 $i$，现在计算的是第 $x + 2$ 轮做完第 $i$ 步的答案，合法的位置数是每维的合法位置乘起来。
将 $x$ 看作自变量，枚举 $i$，第 $x$ 轮走了 $i$ 步的答案是 $f(x) = \prod_j (tot_{j, i} - (a_j - b_j) * x)$，$tot_{j, i}$ 表示第 $j$ 维走了 $i$ 步的合法位置数
$\prod$ 写作 $\sum$, $f(x) = \sum_i c_i x^i$，最终答案即为 $\sum_i c_i (\sum\limits_{i = 1}^{mx} x_i)$（$mx$ 是走的轮数上限。
后面这玩意是个自然数幂和，$k \leq 3$ 时有通项公式，$k > 3$ 时可以预处理因为题目保证 $max_{w_i} \leq 1e6$.
$O(nk^2)$，乘法是 $k^2$, 听说因为 $F$ 变化量小，通过什么拉格朗日插值可以做到 $O(nk)$（蒟蒻不会内个